package LC;

import java.util.Scanner;

/**
 * https://leetcode.com/problems/sqrtx/description/
 * Implement int sqrt(int x).
 * Compute and return the square root of x.
 */
public class LC_069_Sqrt_x_JavaAPI_BinarySearch {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(Solution_1.mySqrt(n));
            System.out.println(Solution_2.mySqrt(n));
        }
        sc.close();
    }

    static class Solution_1 {
        private static int mySqrt(int x) {
            return (int) Math.sqrt(x);
        }
    }

    static class Solution_2 {
        static int mySqrt(int x) {
            long low = 0;
            long high = x / 2 + 1;
            long tmp;
            long mid;
            while (low <= high) {
                mid = (low + high) / 2;
                tmp = mid * mid;
                if (tmp == x)
                    return (int) mid;
                else if (tmp > x)
                    high = mid - 1;
                else if (tmp < x)
                    low = mid + 1;
            }
            return (int) high;
        }
    }
}
